Leonardo's Prime Numbers: Hackerrank Solution

I came across this problem on Hackerrank, and although the problem itself is tagged as "easy", offering just 10 points to the solver, it contains a lot of hidden things behind it, which were quite fun to explore.

Starting out: Naive solution #

As we will treat every problem in this blog, the solution of this one too, will be treated with a naive solution. However, the naive solution for this particular problem is so annoying that it appears to break all bounds of time and space requirements, and simply would not pass. Therefore, instead of giving it a formal introduction with code, I will try to put it in terms of plain algorithm.

1. Start
2. Define function isPrime(n) that returns true if n is prime and false if not.( exercise left to reader, hints given below )
3. for an input number n:
		let maximumCountOfPrimes = 0
		for all numbers below n as j:
			let primeCountForJ = 0
			for all numbers below j as k:
				if j is divisible by k and isPrime(k) is true:
					primeCountForJ += 1
			maximumCountOfPrimes = max(maximumCountOfPrimes, primecountForJ)
		return maximumCountOfPrimes

As one can see, the solution just won't scale at all. No further comments.

Improvement with Sieve of Eratosthenes: #

When one sees the word "prime" in any competitive programming context, the mind immediately wanders off to Sieve of Eratosthenes. The Sieve method is a very effective and quick method of finding out primes. We can modify the sieve method slightly to find the maximum prime count in O(n) time for any given number n, with a bit of preprocessing.

The change we make to the sieve is this: previously, we just marked a number as "prime" or "not prime" while marking every multiplication of a prime number as "not prime".

We change the array first. Instead of storing boolean values for every number, we store integer values for every number which denotes the number of prime factors of that particular number. And instead of marking every multiplication of a given prime number as "not prime", we instead add an increment to the default value of 0, which denotes the number of factors of a given number. For prime numbers, the value would be 1, as they are their own factors.

The question states that the max value of n can be 10^18, which is around 2^60. Storing that many integers would take a huge amount of space, which is not feasible considering our solution.

Enter Mathematics - Highly Composite Numbers: #

Highly composite numbers are just what they sound like: Highly composite. The "high"ness of a composite number is determined by this - it should have more factors than all preceding numbers. Now that you know about this, the problem seems familiar.

This question is actually asking for the number of prime factors of the most highly composite number within a given range. Now, the problem might be daunting at first, but we uncover yet another clue with a careful google search.

Primorial Function - The final solution: #

According to good ol' wikipedia:

Primorial Function denoted by “#”, is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function only multiplies prime numbers.

Now let's analyse our problem further to see if it fits this definition. Our question has asked us to find a solution, that involves the "maximum number of prime factors". The recurrence of the prime factors are not taken into consideration, but their occurrence is taken into consideration. For an example, 2x2x2 and 2 are the same, because a single factor, 2 is present as the prime factor.

Looking at the definition of Primorials in wikipedia, we come to find the same thing.

The graph above shows the values of primorial functions with respect to the n-th prime number. In the final case, the 14th primorial value is equal to 10^14, approximately.

In our case, we need values upto 10^18, so let's google out the first 20 prime numbers. Adding them to a list, we can check any number for it's maximum number of primes by simply multiplying primes until the value is less than or equal to the given number.

Enough words, the code is given below:

primesList = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
def primeCount(n):
    # Using primorial function
    x = 1; 
    i = 0;
    while ( x <= n  and i < 20 ):
        x = x * primesList[i];
        i += 1;

    return i - 1;

Ta-da!

Done.

Footnotes: #

• The code above is written for python.
• The list contains the first 20 prime numbers, although the first 16 would do perfectly okay.